

/**
 * @author zx
 * @date date 2019-12-01 14:02:58
 * -----------------
 * 本方法关键点在于每次快排的最后pivot所在的位置都会是这一局中的第k大
 * -----------------
 */
public class SearchKth {
    /**
     * -----------------
     * 返回最后pivot数的位置，也就是pivot最后会放在j最后的位置上
     * 递减排序，在pivot之前的都比pivot大
     * -----------------
     * @param array
     * @param low
     * @param high
     * @return
     */
    private static int quickSort(int[] array, int low, int high){
        int i = low, j = high;
        int pivot = array[low];
        while (i < j) {
            while(array[j] < pivot && i < j) j--;
            array[i] = array[j];
            while (array[i] > pivot && i < j) i++;
            array[j] = array[i];
        }
        array[j] = pivot;
        return j;
    }


    /**
     *
     * @param array
     * @param low
     * @param high
     * @param k
     */
    private  static int select_k(int[] array, int low, int high, int k){
        if(k > array.length || k == 0){
            return -1;//直接退出
        }

        if(low == high){
            return array[low];
        }
        int current_k; //是当前的第k大
        int partition = quickSort(array,low, high);
        current_k = partition - low + 1;
        if(current_k == k){
            return array[partition];
        }else if(current_k >= k){  //只要在左边，就一直会保证最后一个是当前第k大,并且当前第k大就是全局第k大
            return select_k(array, low, partition - 1, k);
        }else {
            return select_k(array, partition + 1, high, k - current_k);
        }
    }


    public static void main(String[] args) {
        int[] arr = new int[]{5,6,4,3,2,1};
        int result = select_k(arr,0, arr.length - 1, 1);
        System.out.println(result);
    }
}
